package collection;

public class InsertionSorter<T extends Comparable<T>> extends ASorter<T>{

	/**
	 * @purpose: Sort array a in increasing order defined by its element's compareTo method
	 * @require: a!=null
	 * @modify : a
	 * @ensure : a'!=null and a' is sorted version of a
     */
	@Override
	public void sort(T[] a) 
	{
		for (int i = 1; i < a.length; i++)
		{	// loop invariant: 0<=i<=a.length && a[0]...a[k] are sorted for 1<=k<=i-1
			insert(i, a);
		}

		return ;
	}

	/** 
	 * @purpose: Given a[0]...a[i-1] are sorted, insert a[i] into a[0]...a[i-1] such that a[0]...a[i] are all sorted
	 * @require: a!=null && 0<i<a.length && a[0]...a[i-1] are already sorted
	 * @modify : a
	 * @ensure : a'!=null and a'[0]...a'[i] are already sorted
	 */
	private void insert(int i, T[] a) 
	{
		// find the position to insert
		int pos = i-1;
		while( pos >= 0 && a[i].compareTo(a[pos])<0 )
		{	// loop	invariant: -1<=pos<=i-1 && a[i]<=a[pos+1]<=...a[i-1] 
			pos -= 1;
		}
		pos += 1;
		
		// shift all the data that ranked after a[i] to the right by 1 cell
		T temp = a[i];
		for (int j = i; j >= pos + 1; j--)
		{	// loop invariant: 0<=pos<=i && pos<=j<=i && a[k] = a[k-1] for j+1<=k<=i
			a[j] = a[j-1];
		}
		
		// insert the data into the right position
		a[pos] = temp;
	}

	/**
	 * @purpose: return a sorted version of the given list, sorted by increasing order defined by its element's compareTo method
	 * @require: l != null
	 */
	@Override
	public IList<T> sort(IList<T> l) 
	{	
		if (l.isEmpty())
		{
			return l;
		}
		else
		{
			return insert(l.first(), sort(l.rest()));
		}
	}

	/**
	 * @purpose: return a new sorted list with item inserted to sortedList, sorted by increasing order defined by its element's compareTo method
	 * @require: sortedList != null
	 */
	private IList<T> insert(T item, IList<T> sortedList) 
	{
		if (sortedList.isEmpty())
		{
			return new ConsList<T>(item, new MTList<T>());
		}
		else
		{
			if (item.compareTo(sortedList.first()) <= 0)
			{
				return new ConsList<T>(item, sortedList);
			}
			else
			{
				return new ConsList<T>(sortedList.first(), insert(item, sortedList.rest()));
			}
		}
	}

	@Override
	public <N extends ANode<T>> void sort(ILinkedList<N, T> llist) 
	{	
		if (llist.isEmpty())
		{
			return ;
		}

		N curNode = llist.getFirst();
		while(curNode != null)
		{
			N nextNode = llist.getNext(curNode);
			insert(llist, curNode);
			curNode = nextNode;
		}
	}

	private <N extends ANode<T>> void insert(ILinkedList<N, T> llist, N curNode) 
	{
		N iterNode = llist.getPrev(curNode);;
		while(iterNode != null)
		{
			if (curNode.getElement().compareTo(iterNode.getElement()) >= 0)
				break;
			
			iterNode = llist.getPrev(iterNode);
		}
		llist.remove(curNode);
		
		if (iterNode == null)
		{
			llist.addFirst(curNode);
		}
		else
		{
			llist.addAfter(iterNode, curNode);
		}
	}

}
